\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{epsf}
\usepackage{color}
\usepackage{graphics}
\usepackage{graphicx}
\usepackage{pdfcompat}
\usepackage{makeidx}
\usepackage{url}

\definecolor{darkblue}{rgb}{0,0,.75}
\definecolor{darkred}{rgb}{.85,0,0}
\renewcommand{\topfraction}{0.99}       % 99% of page top can be a float
\renewcommand{\bottomfraction}{0.99}    % 99% of page bottom can be a float
\renewcommand{\textfraction}{0.01}      % at least 1% of page must to text
\renewcommand{\floatpagefraction}{0.99}  % and the remaining can be a float

\makeindex
\begin{document}

\begin{center}
\vspace*{1in}
{\Huge \textcolor{red}{\textbf{CREAM \& SUGAR}}}

\bigskip
\bigskip
{\color{blue}
{\LARGE A {\bf C}ompact {\bf RE}targetable {\bf A}bstract {\bf M}achine}

\medskip

{\LARGE \it and}

\medskip

{\LARGE A {\bf SU}itably {\bf G}eneric {\bf A}bstract {\bf R}epresentation}
}

\bigskip
C. R. Ramakrishnan\\
\url{cram@cs.stonybrook.edu}\\
\date
\medskip

\end{center}
\vspace*{0.7in}

\noindent
CREAM is a stack-based abstract machine for executing
{\tt Decaf} programs. CREAM is 
loosely based on the Java Virtual Machine\footnote{Java
is a trademark of Sun Microsystems Inc. For documentation
on Java and JVM, please see the official Javadocs website:
{\tt http://java.sun.com/docs}.} (JVM): it shares 
much of the memory organization as well as many instructions
and instruction formats with the JVM. CREAM is meant for
use in compiler course projects, and retains only the overall flavor
of JVM. For instance,
there are no instructions to invoke virtual methods (which require
dynamic method resolution) or to raise and handle exceptions.
On the other hand, CREAM has additional instructions
(and has changed the formats of a few others) to
simplify compilation.

SUGAR is an assembly language for CREAM. Source {\tt Decaf}
programs are translated into SUGAR programs, which are then
executed using CREAM.
Although designed to execute {\tt Decaf} programs,
CREAM and SUGAR are relatively general.
For instance, many C programs can be translated
into SUGAR programs. Section~\ref{sec:examples}
contains an example of one such translation.
Section~\ref{sec:exec} describes how to execute
and debug SUGAR programs.

\sloppypar
\paragraph{Availability:}
An interpreter for CREAM is available 
from \url{http://www.cs.sunysb.edu/~cram/cream}
in source code form.
At the present time, you may freely copy and modify the
software, but cannot redistribute it. If there is sufficient
interest, the software will be made available under GNU
Library Public License, which will give rights for
modification and redistribution. Please send mail to
\url{cram@cs.sunysb.edu} if you plan to use the software
or the accompanying documentation for a course project.

The interpreter is written in C, and has been tested
on the following 32-bit Unix systems: SunOS 4.x, Solaris,
Linux and Free BSD.
The implementation is relatively straightforward and hence
should be easily portable to other platforms. Please
send mail to \verb+cram@cs.sunysb.edu+ regarding any
bugs or installation problems.

\section{Components of CREAM}
\label{sec:memorg}

CREAM consists of:
\begin{itemize}
\item A {\em stack\/} (parameters, temporaries)
\item A {\em heap\/}  (dynamically allocated data)
\item A {\em static area\/}   (statically allocated data)
\item A small set of {\em registers\/}
\item A {\em method area\/} (code)
\item An {\em instruction set\/}
\end{itemize}
Below, we describe the first five components at greater detail.
The instruction set is described in the next section.

These are logical components of the abstract machine, and
does not specify any specific implementation strategy. For
example, the stack may be implemented as a contiguous stack
(array) or as a linked list: the abstract machine itself
is oblivious to such underlying implementation techniques.

\subsection{Primitive Data Types}
Four primitive data types are recognized by CREAM: integers,
floating point values, object and array references and
(references to) strings. All primitive data types are
32-bit quantities: integers are signed, float values are
single precision, and object array and string references
are (implementation dependent) 32-bit values values.

\subsection{The Stack}
The stack is used to store parameters for operations, arguments
to methods, local as well as temporary variables and saved values
of registers. 
The stack can be logically divided into a number of activation records.
Each record corresponds to an activation of a method,
and contains the local variables of the method (including its
parameters), some book-keeping information (links to previous
records, etc.) and a scratch area to hold temporary values,
called the {\em operand stack}.
The operand stack always appears at the top of the stack.

\subsubsection*{The Operand Stack}
The operand stack is used as a scratch area for computation.
The arguments and return values of CREAM instructions are
stored on the operand stack. For example, the {\tt iadd} instruction
adds the top two words on the operand stack and replaces them
with their sum. The operands themselves are placed there by
other instructions (even nested computations).


In CREAM, parameters are treated simply as local variables.
Local variables are numbered contiguously, starting from 0.
In an activation of a $n$-argument method, 
local variable 0 corresponds to parameter 0,
local variable 1 to parameter 1, and so on up to
local variable $n$. Local variable $n+1$ onwards are
variables declared in the body of the method.

The instruction set contains instructions to load
the value of local variables on the operand stack and
to store the value on top of the operand stack into local
variables.

Figure~\ref{fig:stack-frame} shows the organization of
an activation record in our implementation of CREAM.
\begin{figure}[htbp]
\begin{center}
\mbox{
\includegraphics[height=4.5in]{\graphicsfile{stack}}
}
\caption{Activation record in our implementation of CREAM.}
\label{fig:stack-frame}
\end{center}
\end{figure}


\subsection{The Heap}
The heap holds class instances and arrays. Each class instance
or array is stored in a region of appropriate size in the
heap. The instances and arrays are referenced using {\em handles\/}:
the handles can be thought of as the id of the corresponding region.
Each non-static field in a class is given a unique offset; the field
of an instance is accessed using the handle of the instance and
the field's offset.
An element of an array is accessed using the handle of the array
and the element's index.


\subsection{The Static Area}
The static fields of classes and string constants are stored in 
the static area. The proper placement of these fields is
determined by the compiler. The static area is divided into
many contiguous regions, one for each class and one common region
for all string constants. The regions themselves are numbered
starting from 0. String constants are stored in
Region 0, as a null-terminated sequence of 8-bit characters.
Each class is associated with a unique, fixed,  region number.
Each static field in the class is located
at a fixed offset within that region. So each static
field is uniquely known by a (region number, offset) pair.
A {\em Region Table\/} is used to map region numbers
to the corresponding locations in the static area.


\subsection{Registers}
The registers of CREAM represent the run-time
state of the abstract machine. CREAM's registers are:
\begin{itemize}
\item {\tt sp}: {\bf stack pointer}, a pointer to the top of the stack.
\item {\tt bp}: {\bf base pointer}, a pointer to the zero-th local variable
		of the currently executing method,
\item {\tt ep}: {\bf environment pointer}, a pointer to the current
		environment (along with its book-keeping fields).
\item {\tt pc}: {\bf program counter}, a pointer to the next instruction
		to be executed.
\item {\tt hp}: {\bf heap pointer}, a pointer to the first free
		area in the heap.
\end{itemize}
Unlike other (real) machines, CREAM does not permit direct manipulation
(read or write) of any of these registers; these registers are implicitly
modified by executing a sequence of the abstract machine instructions.
It is this abstraction that allows the implementor to choose the
most appropriate run-time organization.



\subsection{The Method Area}
The compiled code for each method in a program
resides in the method area. In our implementation,
each instruction is realized as a call to a C-function, and 
each method is compiled into a C function;
We let the C compiler and the linker-loader decide where
to place the code.

\newcommand{\stackdesc}[2]{
	{\bf Stack:} { $\ldots$ {\it #1\/} {\tt \ $\Longrightarrow$\ } 
			$\ldots$  {\it #2} }
}

\newcommand{\instruction}[6]{
	\item[{\color{darkblue}#1}]
	{#2}\\[0.5ex]
	{\bf Syntax:} {\tt #3;}\\[0.5ex]
	\stackdesc{#4}{#5}\\[0.5ex]
		{#6}
\index{#1}
}

\section{CREAM Instruction Set}
\label{sec:instructions}

Each instruction of CREAM is described using the following format:

\begin{description}
\instruction{sample}{A {\em short\/} description}
	{sample(operand1, operand2, ...)}
	{,value1, value2}{,value3}
	{A {\em longer\/} description that explains special features of
	this instruction if any.}
\end{description}

The ``Stack:'' line of an instruction description captures visually
the effect of that instruction's execution on the stack.
For example,
\begin{quote}
\stackdesc{, value1, value2}{, value3}
\end{quote}
denotes that the instruction expects {\it value2\/} on top of
stack and {\it value1\/} just beneath it; and that execution
of the instruction results in replacing the two values on stack
with {\it value3}. The rest of the stack is represented by
``...'' and is left unchanged.

\subsection{Load Immediate Values on Stack}

\begin{description}

\instruction{ildc}
	{Load integer constant}
	{ildc({\it const\/})}
	{}{, const}
	{Push 32-bit integer constant {\it const\/} on operand stack.}

\instruction{fldc}
	{Load floating point constant}
	{ildc({\it const\/})}
	{}{, const}
	{Push 32-bit floating-point constant {\it const\/} on operand stack.}

\instruction{null}
	{Load null value}
	{null()}
	{}{, null}
	{Push the {\it null\/} object on operand stack.}

\end{description}

\subsection{Load/Store Local Variables to/from Stack}

\begin{description}
\instruction{load}
	{Load value from local variable}
	{load()}
	{, locvar}{, value}
	{Push the value {\it value\/} of local variable {\it locvar\/} on
	stack. {\it locvar\/} is the offset of the local variable from
	the base of the current activation record. The offset itself
	may be placed on the stack by a previous {\tt ildc} instruction.}

\instruction{store}
	{Store value to local variable}
	{store()}
	{, locvar, value}{, value}
	{Place the value {\it value\/} in the  local variable {\it locvar\/}.
	 Remove {\it locavar\/} from stack, but retain {\it value\/} on top
	 of stack.
	}

\end{description}

\subsection{Arrays}

\begin{description}


\instruction{aload}
	{Load value from array}
	{aload()}
	{, array, index}{, value}
	{{\it array\/} is a handle to an array in heap; the value at
	position number {\it index\/} is retrieved and pushed on stack.}

\instruction{astore}
	{Store value into an array}
	{astore()}
	{, array, index, value}{, value}
	{{\it array\/} is a handle to an array in heap; {\it value\/} is
	stored at position number {\it index\/} in {\it array}.
	Remove array handle and index from stack, but retain {\it value\/}
	on top of stack.}

\instruction{newarray}
	{Allocate a new array}
	{newarray({\it n\/})}
	{, size-1, size-2, ..., size-n}{handle}
	{An $n$-dimensional array is created and its {\it handle\/}
	 is pushed on stack. {\it size-i\/} specifies
	 the size in the $i$-th dimension. $n$ must be an integer, greater or
	 equal to $1$. 

	 Examples:

	 To create a new array corresponding to {\tt new int[5]}, the
	 following code is used:
	 \begin{quote}
		{\tt	ildc(5);\\
			newarray(1);}
	 \end{quote}
	 To create a new array corresponding to {\tt new int[10][5][]}, the
	 following code is used:
	 \begin{quote}
		{\tt	ildc(10);\\
			ildc(5);\\
			newarray(2);}
	 \end{quote}
	}

\end{description}

\subsection{Stack Manipulation}

\begin{description}
\instruction{nop}
	{Do nothing.}
	{nop()}
	{}{}
	{No operation.}

\instruction{pop}
	{Pop top element of stack}
	{pop()}
	{, value}{}
	{Pop top element of stack; note that the value is simply discarded.}

\instruction{dup}
	{Duplicate top element of stack}
	{dup()}
	{, value}{, value, value}
	{The top element of stack is duplicated.}

\instruction{dup2}
	{Duplicate top two elements of stack}
	{dup2()}
	{, value1, value2}{, value1, value2, value1, value2}
	{The top two elements of stack are duplicated.}

\instruction{swap}
	{Swap top two elements of stack}
	{swap()}
	{, value1, value2}{, value2, value1}
	{The values of the top two elements of the stack are interchanged.}

\instruction{swap1\_2}
	{Exchange top element of stack with next two elements}
	{swap1\_2()}
	{, value1, value2, value3}{, value3, value1, value2}
	{The value of the top element of the stack is ``slid under'' the
	next two elements.}

\end{description}

\subsection{Arithmetic operations}
\begin{description}

\instruction{iadd}
	{Integer add}
	{iadd()}
	{, value1, value2}{, result}
	{{\it value1\/} and {\it value2\/} should be integers.
	 The values are added and are replaced on stack by their sum.
	}

\instruction{isub}
	{Integer subtract}
	{isub()}
	{, value1, value2}{, result}
	{{\it value1\/} and {\it value2\/} should be integers.
	The values are replaced on stack
	by {\it value1} $-$ {\it value2}.
	}

\instruction{imul}
	{Integer multiply}
	{imul()}
	{, value1, value2}{, result}
	{{\it value1\/} and {\it value2\/} should be integers.
	 The values are multiplied and are replaced on stack
	 by their product.
	}

\instruction{idiv}
	{Integer division}
	{idiv()}
	{, value1, value2}{, result}
	{{\it value1\/} and {\it value2\/} should be integers.
	The values are replaced on stack
	by {\it value1} $/$ {\it value2}.
	}

\instruction{ineg}
	{Integer negation}
	{ineg()}
	{, value}{, result}
	{{\it value\/} should be an integer.
	It is replaced on stack
	by $-$ {\it value}.
	}

\instruction{fadd}
	{Floating-Point add}
	{fadd()}
	{, value1, value2}{, result}
	{{\it value1\/} and {\it value2\/} should be floating-point values.
	 The values are added and are replaced on stack by their sum.
	}

\newpage
\instruction{fsub}
	{Floating-Point subtract}
	{fsub()}
	{, value1, value2}{, result}
	{{\it value1\/} and {\it value2\/} should be floating-point values.
	The values are replaced on stack
	by {\it value1} $-$ {\it value2}.
	}

\instruction{fmul}
	{Floating-Point multiply}
	{fmul()}
	{, value1, value2}{, result}
	{{\it value1\/} and {\it value2\/} should be floating-point values.
	 The values are multiplied and are replaced on stack
	 by their product.
	}

\instruction{fdiv}
	{Floating-Point division}
	{fdiv()}
	{, value1, value2}{, result}
	{{\it value1\/} and {\it value2\/} should be floating-point values.
	The values are replaced on stack
	by {\it value1} $/$ {\it value2}.
	}

\instruction{fneg}
	{Floating-point negation}
	{ineg()}
	{, value}{, result}
	{{\it value\/} should be a floating-point value.
	It is replaced on stack
	by $-$ {\it value}.
	}

\instruction{int2float}
        {Floating-point conversion}
	{int2float()}
	{, value}{, result}
	{{\it value\/} should be an integer value.
	It is replaced on stack
	by the equivalent floating point value.
	}

\end{description}

\subsection{Logical operations}
CREAM uses $1$ to denote the boolean value true and $0$ to denote false.

\begin{description}
\instruction{and}
	{Boolean And}
	{and()}
	{, value1, value2}{, result}
	{{\it value1\/} and {\it value2\/} should be boolean values.
	The values are replaced on stack
	by their conjunction.
	}
\instruction{or}
	{Boolean Or}
	{or()}
	{, value1, value2}{, result}
	{{\it value1\/} and {\it value2\/} should be boolean values.
	The values are replaced on stack
	by their disjunction.
	}
\instruction{not}
	{Boolean negation}
	{not()}
	{, value}{, result}
	{{\it value\/} should be a boolean value. It is replaced on
	stack by its negation.
	}
\end{description}

\subsection{Comparison operations}
\begin{description}
\instruction{iequal}
	{Integer Equal}
	{iequal()}
	{, value1, value2}{, result}
	{{\it value1\/} and {\it value2\/} should be integers.
	{\it result} is set to $1$ if {\it value1\/} and 
	{\it value2\/} are the same, and $0$ otherwise.
	}
	
\instruction{inotequal}
	{Integer Not Equal}
	{inotequal()}
	{, value1, value2}{, result}
	{{\it value1\/} and {\it value2\/} should be integers.
	{\it result} is set to $1$ if {\it value1\/} and 
	{\it value2\/} are distinct, and $0$ otherwise.
	}
	
\instruction{ilt}
	{Integer Less Than}
	{ilt()}
	{, value1, value2}{, result}
	{{\it value1\/} and {\it value2\/} should be integers.
	{\it result} is set to $1$ if {\it value1\/} $<$ {\it value2\/},
	and $0$ otherwise.
	}
	
\instruction{ilte}
	{Integer Less Than or Equal}
	{ilte()}
	{, value1, value2}{, result}
	{{\it value1\/} and {\it value2\/} should be integers.
	{\it result} is set to $1$ if {\it value1\/} $\leq$ {\it value2\/},
	and $0$ otherwise.
	}
	
\instruction{igt}
	{Integer Greater Than}
	{igt()}
	{, value1, value2}{, result}
	{{\it value1\/} and {\it value2\/} should be integers.
	{\it result} is set to $1$ if {\it value1\/} $>$ {\it value2\/},
	and $0$ otherwise.
	}
	
\instruction{igte}
	{Integer Greater Than or Equal}
	{igte()}
	{, value1, value2}{, result}
	{{\it value1\/} and {\it value2\/} should be integers.
	{\it result} is set to $1$ if {\it value1\/} $\geq$ {\it value2\/},
	and $0$ otherwise.
	}

\newpage
\instruction{fequal}
	{Floating-Point Equal}
	{fequal()}
	{, value1, value2}{, result}
	{{\it value1\/} and {\it value2\/} should be floating-point values.
	{\it result} is set to $1$ if {\it value1\/} and 
	{\it value2\/} are the same, and $0$ otherwise.
	}
	
\instruction{fnotequal}
	{Floating-Point Not Equal}
	{fnotequal()}
	{, value1, value2}{, result}
	{{\it value1\/} and {\it value2\/} should be floating-point values.
	{\it result} is set to $1$ if {\it value1\/} and 
	{\it value2\/} are distinct, and $0$ otherwise.
	}
	
\instruction{flt}
	{Floating-Point Less Than}
	{flt()}
	{, value1, value2}{, result}
	{{\it value1\/} and {\it value2\/} should be floating-point values.
	{\it result} is set to $1$ if {\it value1\/} $<$ {\it value2\/},
	and $0$ otherwise.
	}
	
\instruction{flte}
	{Floating-Point Less Than or Equal}
	{flte()}
	{, value1, value2}{, result}
	{{\it value1\/} and {\it value2\/} should be floating-point values.
	{\it result} is set to $1$ if {\it value1\/} $\leq$ {\it value2\/},
	and $0$ otherwise.
	}
	
\instruction{fgt}
	{Floating-Point Greater Than}
	{fgt()}
	{, value1, value2}{, result}
	{{\it value1\/} and {\it value2\/} should be floating-point values.
	{\it result} is set to $1$ if {\it value1\/} $>$ {\it value2\/},
	and $0$ otherwise.
	}
	
\instruction{fgte}
	{Floating-Point Greater Than or Equal}
	{fgte()}
	{, value1, value2}{, result}
	{{\it value1\/} and {\it value2\/} should be floating-point values.
	{\it result} is set to $1$ if {\it value1\/} $\geq$ {\it value2\/},
	and $0$ otherwise.
	}

\instruction{oequal}
	{Object Equal}
	{oequal()}
	{, value1, value2}{, result}
	{{\it value1\/} and {\it value2\/} should be object references.
	{\it result} is set to $1$ if {\it value1\/} and 
	{\it value2\/} are the same (i.e., same addresses), and $0$ otherwise.
	}

\newpage
\instruction{onotequal}
	{Object Not Equal}
	{onotequal()}
	{, value1, value2}{, result}
	{{\it value1\/} and {\it value2\/} should be object references.
	{\it result} is set to $1$ if {\it value1\/} and 
	{\it value2\/} are the distinct (i.e., different addresses),
	and $0$ otherwise.
	}
	
\end{description}

\subsection{Control}
\begin{description}
\instruction{jmp}
	{Unconditional Jump}
	{jmp({\it label\/})}
	{}{}
	{{\it label\/} is some symbolic address in the code for current
	method.	Control is transferred to the given {\it label\/}. 
	}
	
\instruction{jz}
	{Jump on Zero}
	{jz({\it label\/})}
	{, value}{}
	{{\it label\/} is some symbolic address in the code for current
	method.	If {\it value\/} is $0$, 
	control is transferred to the given {\it label\/}. 
	Otherwise, control goes to the next instruction in code.
	In either case, {\it value\/} itself is removed from the stack.
	}
	
\instruction{jnz}
	{Jump on Non-zero}
	{jnz({\it label\/})}
	{, value}{}
	{{\it label\/} is some symbolic address in the code for current
	method.	If {\it value\/} is {\em not\/} $0$, 
	control is transferred to the given {\it label\/}. 
	Otherwise, control goes to the next instruction in code.
	In either case, {\it value\/} itself is removed from the stack.
	}
	

\end{description}

\subsection{Method Invocation}
\begin{description}
\instruction{call}
	{Method Invocation}
	{call({\it method\/})}
	{}{}
	{Invoke a method {\it method}, after 
	the arguments, including the object, are pushed on stack.
	 Control is transferred to the first instruction in the body of
	 {\it method\/}. 
	 The stack itself is left unchanged.
	 The next instruction in the caller (the point of
	 return) is stored on a separate (invisible) control stack.
	}

\instruction{ret}
	{Method Return}
	{ret()}
	{, current-activation-record, value}{, value}
	{Returns control to callee method (using information stored
	 in separate control stack). The current activation record
	 is discarded, and the return value (top of input stack) is
	 then placed on top of the new stack.
	}

\instruction{new\_env}
	{Set up new environment}
	{new\_env({\it nargs, nlocals})}
	{}{, local-variables, book-keeping-info}
	{This instruction is used to set up a new activation record
	 upon entry to a method. This is the only place where this instruction
	 is used. {\it nargs\/} specifies the number of arguments to the 
	 method and {\it nlocals\/} specifies the number of local variables
	 used in the method. It allocates space for the local variables
	 on top of the current stack, and adds book-keeping information
	 for environment management (saved values of base pointer etc.).
	 The base pointer is then set to point to the first argument on stack
	 (position computed using {\it nargs\/}). The environment
	 pointer is set to point to the book-keeping information, and
	 the stack pointer is set to the new stack top. The operand area
	 (on top of book-keeping information) is initialized to null.
	}

\end{description}

\subsection{Object Access}
\begin{description}
\instruction{newobj}
	{Allocate an object}
	{newobj({\it size\/})}
	{}{, handle}
	{A new object is allocated on the heap; the size of the allocated
	 area is given by {\it size\/}. The handle of the newly-allocated
	 area (i.e., its base address) is pushed on stack.}
 
\instruction{putfield}
	{Set field in object}
	{putfield()}
	{, handle, offset, value}{, value}
	{ {\it handle\/} is a handle for an object: i.e., a reference to
	 an instance of some class.
	 {\it value\/} is stored in 
	 the field at the specified {\it offset\/} in the object referred
	 to by {\it handle\/}. As in the case of other {\tt store}
	 instructions, the value is retained as top of the stack.
	}

\instruction{getfield}
	{Set field in object}
	{getfield()}
	{, handle, offset}{, value}
	{ {\it handle\/} is a handle for an object: i.e., a reference to
	 an instance of some class.
	 The value of 
	 the field at the specified {\it offset\/} in the object referred
	 to by {\it handle\/} is pushed on stack.
	}

\instruction{putstatic}
	{Set static field in class}
	{putstatic()}
	{, class-number, offset, value}{, value}
	{ {\it class-number\/} is the unique number given to each class
		 by the compiler.
	  The field specified by this instruction is the one in
	  Region {\it class-number\/} of the static area; the offset
	  of the field in this region is given by {\it offset\/}.
	  {\it value\/} is stored in this field.
	  The value is retained as top of the stack.
	}

\newpage
\instruction{getstatic}
	{Set static field in class}
	{getstatic()}
	{, class-number, offset}{, value}
	{ {\it class-number\/} is the unique number given to each class
		 by the compiler.
	  The field specified by this instruction is the one in
	  Region {\it class-number\/} of the static area; the offset
	  of the field in this region is given by {\it offset\/}.
	  The value stored in this field is pushed on stack.
	}

\end{description}

\section{SUGAR}
\label{sec:sugar}
As its name implies, SUGAR adds syntactic sugar to CREAM's instruction set.
The overall structure of SUGAR programs resemble that of C programs.
Each SUGAR program consists of four sections:
\begin{itemize}
\item Header section
\item Code section
\item Main program definition
\item Static area initialization
\end{itemize}
Each of these sections are described below.

\subsection{Header section}
The header section always consists of the following code:
\begin{quote}
\begin{verbatim}
#include "machine.h"
\end{verbatim}
\end{quote}


\subsection{Code section}

SUGAR code consists of a set of procedure definitions. Each definition
contains the code for a method, and is of the form:
\begin{quote}
\begin{tabbing}
\=xxx\=xxx\kill
\> {\tt entry {\it method-name\/}()}\\
\> {\tt \{}\\
\> \> {\it Sequence of {\rm CREAM} instructions}\\
\> {\tt \}}\\
\end{tabbing}
\end{quote}
The method-name in a SUGAR program is a unique symbolic name assigned by
the compiler for each method in the source program.

Apart from CREAM instructions, the body of SUGAR code definitions
may contain symbolic {\it labels}. These labels are destinations
of {\tt jmp} and {\tt jz} instructions in the code. Following is
a fragment of SUGAR code with labels. 
\begin{quote}
\begin{verbatim}
   ....
   ilt();
   jz(label1);
   ....

 label1:
   ildc(0);
   ....
   jmp(label1);
   ...
\end{verbatim}
\end{quote}
SUGAR code can also contain C-style comments. 
See Section~\ref{sec:examples}
for examples of complete SUGAR programs.



\subsection{Main Program}

Each SUGAR program contains one main procedure called {\tt sugar\_main()}.
When a SUGAR program is executed, CREAM first initializes the various
memory areas and registers and makes a call to {\tt sugar\_main()}.
The procedure {\tt sugar\_main()} in turn invokes one or more
SUGAR procedures.

Conventionally, a {\tt Decaf} to SUGAR compiler translates the {\tt main()}
method in the {\tt Decaf} program into the code for {\tt sugar\_main()}.


\subsection{Static Area Initialization}

This section of a SUGAR program contains
code to initialize of the Static Area of CREAM.
The code in this section has the form:
\begin{quote}
\begin{tabbing}
\=xxx\=xxx\kill
\> {\tt entry static\_area\_initialization()}\\
\> {\tt \{}\\
\> \> {\it String table initialization}\\
\> \> {\it Class table initialization}\\
\> {\tt \}}\\
\end{tabbing}
\end{quote}

String table initialization consists of code to load
the strings used by the program in Region~0 of the Static Area.
The code is of the form
\begin{quote}
\begin{tabbing}
\=xxx\=xxx\kill
\> \> {\tt strcpy("{\it string-value\/}", \&(static\_area[{\it offset\/}]));}
\end{tabbing}
\end{quote}
The value of {\it offset\/} is typically computed by the compiler.

Following the string table initializations (if any)
is code to initialize the region table to refer to the appropriate
class numbers. Each statement of the code is of the form:
\begin{quote}
\begin{tabbing}
\=xxx\=xxx\kill
\> \> {\tt region\_table[{\it class-number\/}] = {\it offset\/};}
\end{tabbing}
\end{quote}
The region table records a map from 
classes to specific regions in the static area.
The map itself (and hence the values of {\it class-number\/} and
{\it offset\/} of each initialization statement)
is determined by the compiler.

\section{Examples}
\label{sec:examples}

\subsection{Translation of a {\tt Decaf} Program}
Consider the following {\tt Decaf} program:
\begin{quote}
\begin{verbatim}
class List {
  List next;
  int length() {
    if (next == null)
      return 1;
    else
      return 1 + next.length();
  }

  public static void main() {
     List list;
     int n;

     list = new List();
     n = list.length();
  }
}
\end{verbatim}
\end{quote}
The above program can be translated into the following SUGAR code.
(Note that a compiler may generate a different sequence of
instructions that have the same effect.)
\begin{quote}
\begin{verbatim}
#include <stdio.h> 
#include "machine.h"
#include "inst.h"
entry static_area_initialization() {
  region_table[0] = 0;
  region_table[1] = 0;
}

entry sugar_main() { 
  new_env(0,0);      /* main has no arguments or local variables */
  call(main_5);      /* invoke the appropriate main method */
  ret();             /* and return */
}

entry length_4() {
  new_env(1, 0);     /* 1 argument (this) and 0 local variables */

  ildc(0);
  load();            /* get first argument (this) */    
  ildc(0);           /* offset of "next" in List  */
  getfield();        /* get value of next */
  null();            /* push null on stack */
  oequal();          /* if not equal */
  jz(label0);        /*   goto label0 */

  ildc(1);           /* push 1 (return value) on stack */
  ret();

label0:
  ildc(1);           /* push 1 on stack (rhs of +) */
  ildc(0);
  load();            /* get first argument (this) */    
  ildc(0);           /* offset of "next" in List  */
  getfield();        /* get value of next */
  call(length_4);  /* recursive call */
  iadd();            /* add the results */
  ret();

}

entry main_5() {
  new_env(0, 2);     /* 2 local variables, no arguments (note: static method)*/
  ildc(0);           /* l-value of "list" (i.e. its offset in activation rec.*/
  newobj(1);         /* allocate an object of type "List" */
  call(List_8);      /* initialize the object with call to constructor */
  store();           /* store the newly allocated object in "list" */
  pop();             /* remove the list handle from temporaries */
  ildc(1);           /* position of "n" */
  ildc(0);           /* l-value of "list" */
  load();            /* get r-value of "list" */
  call(length_4);    /* call length */
  store();           /* store return value in "n" */
  pop();             /* remove the return value from temporaries */
  null();            /* push dummy value to return from void method */
  ret();
}

entry List_8() {     /* Default List() constructor: identity function */
  new_env(1, 0);     /* has 1 argument (this) and no locals */
  ildc(0);           /* l-value of "this" */
  load();            /* get r-value of "this" */
  ret();             /* return it */
}
\end{verbatim}
\end{quote}



\subsection{Translation of a C program}

SUGAR lives up to the claims of generality made in its name.
Many C programs can be translated into equivalent SUGAR programs.
For example,
consider the following recursive function that computes
{\em Fibanocci\/} numbers:

\begin{quote}
\begin{verbatim}
int fib(int n)
{
  if (n < 2)
    return n;
  else
    return fib(n-1) + fib(n-2);
}
\end{verbatim}
\end{quote}
%
The above function can be mechanically translated to the following
SUGAR code:
%
\begin{quote}
\begin{verbatim}
entry fib()
{
  new_env(1, 0);

  ildc(0);
  load();
  ildc(2);
  ilt();
  jz(label1);

  ildc(0);
  load();
  ret();

 label1:
  ildc(0);
  load();
  ildc(1);
  isub();
  call(fib);

  ildc(0);
  load();
  ildc(2);
  isub();
  call(fib);

  iadd();
  ret();
}
\end{verbatim}
\end{quote}


\section{Executing and Debugging SUGAR Programs}
\label{sec:exec}

An interpreter for CREAM, available from CSE 304/504 course directories,
implements each CREAM instuction
as a C function. A shell script, called {\tt stir},  to compile SUGAR programs
using {\tt gcc} to produce executables is also available
from the course directories.
The script compiles SUGAR programs with ``-g'' option, enabling
symbolic debugging of the code.

Assume that we have a SUGAR program in a file, say {\tt foo.c}.
By invoking {\tt stir -o foo foo.c}, an executable called {\tt foo}
is produced. The code can be debugged using {\tt gdb}, by setting
break points in {\tt foo.c}, and using {\tt next} ({\tt n}) command
of {\tt gdb} to single-step through the CREAM instructions.

Two SUGAR functions, {\tt print\_current\_frame()} and {\tt print\_stack()}
may be used get information on the memory area during program execution.
The contents of the current stack frame can be viewed
at any point in the execution of a SUGAR program under {\tt gdb},
by typing {\tt p print\_current\_frame()} at a {\tt gdb} prompt. 
The contents of the entire stack can be viewed
using the command {\tt p print\_stack()}.
Neither command changes the contents of the stack.

\newpage
\renewcommand{\indexname}{Instruction Index}
\printindex

\end{document}
